Given the root of a binary tree, invert the tree, and return its root.

給一個 tree 的 root 將該 tree 中所有 node 的左右 node 交換。

Example

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

BFS

要解這題要先了解什麼是 BFS (廣度搜尋)，簡單來說就是以 layer 來遍歷 tree，從第一層開始往下一層一層的遍歷整顆 tree。

Coding

function bfs() {
    let queue = [this.root], res = [];
    while (queue.length !== 0) {
      let size = queue.length;
      const levelNode = [];
      while (size) {
        const node = queue.shift();
        levelNode.push(node.val);
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
        size--;
      }
      res.push(...levelNode);
    }
    return res;
}

利用一個 queue 存處每一層的 node，利用 size 紀錄每一層共有幾個 node，並利用 queue 的 FIFO 特性，把該層的每一個 node 拿出來並判斷該 node 是否有 left 或 right node，如果有就將他放近 queue 中。

invertTree

該題也用 bfs 的方式遍歷每一層，把每一層的 left node 和 right node 交換即可

coding - while

var invertTree = function (root) {
  let queue = [root];
  while (queue.length !== 0) {
    let size = queue.length;
    while (size) {
      const node = queue.shift();
      if (!node.left && !node.right) {
        size--;
        continue;
      }
      const tmpL = node.left;
      node.left = node.right;
      node.right = tmpL;
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
      size--;
    }
  }
  return root;
};

Coding - recursion

也可以利用 recursion 的方式先交換 left node 後再交換 right node

function invert(node) {
  if (node === null) return;
  
  const tmp = node.left;
  node.left = node.right;
  node.right = tmp;
  
  invert(node.left);
  invert(node.right);
}

var invertTree = function(root) {
  invert(root)
  return root
}

Time complexity: O(n)